package com.dmall.chapter03.section04;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 暴力解法
 * 时间复杂度：O(n^3)
 * 空间复杂度：O(n)
 * @author xiao1.wang
 * @date 2020-12-01 23:14:47
 */
public class Leetcode15V1 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Set<Set<Integer>> set = new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        Set<Integer> oneSet = new HashSet<>();
                        oneSet.add(nums[i]);
                        oneSet.add(nums[j]);
                        oneSet.add(nums[k]);
                        if (!set.contains(oneSet)) {
                            set.add(oneSet);
                            List<Integer> oneRes = new ArrayList<>();
                            oneRes.add(nums[i]);
                            oneRes.add(nums[j]);
                            oneRes.add(nums[k]);
                            res.add(oneRes);
                        }
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int[] nums = {-5, 1, -10, 2, -7, -13, -3, -8, 2, -15, 9, -3, -15, 13, -6, -10, 5, 6, 11, 1, 13, -12, 14, 6, 11, 4, 13, -14, 0, 11, 1, 10, -11, 6, -11, -10, 8, 2, -3, -13, -6, -9, -9, -6, 11, -8, -9, 1, 13, 9, 9, 3, 13, 0, -6, 1, -10, -15, 3, 5, 3, 11, -8, 0, 2, -11, 5, -13, 6, 9, -11, 7, 8, -13, 8, 4, -6, 14, 13, -15, 1, 7, -5, -1, -7, 5, 7, -2, -3, -13, 10, 7, 13, 9, -8, -8, 13, 12, -6, 4, 7, -10, -12, -8, -8, 11, 11, -6, 3, 9, -14, -11, 2, -4, -5, 10, 8, -13, -7, 12, -10, 10};
        Leetcode15V1 leetcode15 = new Leetcode15V1();
        System.out.println(leetcode15.threeSum(nums));
        long end = System.currentTimeMillis();
        System.out.println((end - start));
    }
}
